package algorithm.leetcode.I201to400;

import java.util.HashSet;
import java.util.TreeSet;

/**
 * i和j之差不超过k
 */

public class Q220 {

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> ts = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            Long u = nums[i] * 1L;
            // 从 ts 中找到小于等于 u 的最大值（小于等于 u 的最接近 u 的数）
            Long l = ts.floor(u);  // 可能为null,所以必须用引用类型,下同
            // 从 ts 中找到大于等于 u 的最小值（大于等于 u 的最接近 u 的数）
            Long r = ts.ceiling(u);
            if(l != null && u - l <= t) return true;
            if(r != null && r - u <= t) return true;
            // 将当前数加到 ts 中，并移除下标范围不在 [max(0, i - k), i) 的数（维持滑动窗口大小为 k）
            ts.add(u);
            // 为什么不会出现new int[]{3,0,-5,3,2}, 3, 1)这种情况,因为如果待删除之前就有add的元素,那么一定会在上面两个if中return true
            if (i >= k) ts.remove(nums[i - k] * 1L);
        }
        return false;
    }


    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<Integer>() {{ add(3);  add(3);}};
        set.remove(3);

        Q220 q220 = new Q220();
        System.out.println(q220.containsNearbyAlmostDuplicate(new int[]{3,0,-5,3,2}, 3, 1));
    }

}
